﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//思路，循环一次就一分钟，变一下
public class Solution994
{
    int min = -1;
    public int OrangesRotting2(int[][] grid)//深度遍历不行
    {
         
        int m= grid.Length;
        int n= grid[0].Length;

        bool havefresh = false;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    //还有新鲜的就返回-1
                    havefresh = true;
                    
                }
            }
        }
        if (!havefresh)//没有新鲜的就返回0
        {
            return 0;
        }
        for (int i= 0; i < m; i++)
        {
            for(int j= 0; j < n; j++)
            {
                if (grid[i][j] == 2)
                {
                    DFS(i, j, grid,0);//开始腐烂
                }
            }
        }
        
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    //还有新鲜的就返回-1
                    
                    return -1;
                }
            }
        }
       


        return min;

    }

    private void DFS(int row, int col, int[][] grid,int depth)
    {
        min=Math.Max(min, depth);
        grid[row][col] = 2;
        

        //右
        if (col < grid[0].Length - 1 && grid[row][col + 1] == 1)
        {

            DFS(row, col + 1, grid, depth+1);
        }

        //下
        if (row < grid.Length - 1 && grid[row + 1][col] == 1)
        {

            DFS(row + 1, col, grid, depth + 1);
        }

        //左
        if (col > 0 && grid[row][col - 1] == 1)
        {

            DFS(row, col - 1, grid, depth + 1);
        }
        //上
        if (row > 0 && grid[row - 1][col] == 1)
        {

            DFS(row - 1, col, grid, depth + 1);
        }

    }


    public int OrangesRotting(int[][] grid)//BFS
    {
        int m = grid.Length;
        int n = grid[0].Length;
        int[][] time = new int[m][];//到达这个点的时间
        for (int i = 0; i < grid.Length; i++)
        {
            time[i] = new int[n];
        }
        Queue<int> queue = new Queue<int>();

        //把开始就腐烂的加入队列
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 2)
                {
                    queue.Enqueue(i);
                    queue.Enqueue(j);
                    time[i][j] = 0;//本来就腐烂的时间是0

                }
            }
        }

        int[][] dirs = [[0, 1],
            [0, -1],
            [1, 0],
            [-1, 0]];
        while (queue.Count > 0)
        {
            int row = queue.Dequeue();//
            int col = queue.Dequeue();//

            for (int dir = 0; dir < 4; dir++)
            {
                int nextRow = row + dirs[dir][0];
                int nextCol = col + dirs[dir][1];

                if(nextRow < 0 || nextCol < 0|| nextRow >= m || nextCol >= n)
                {
                    continue;//跳过
                }
                
                if ( grid[nextRow][nextCol ] == 1)
                {
                    grid[nextRow][nextCol] = 2;//腐烂
                    time[nextRow][nextCol] = time[row][col] + 1;
                    //入队
                    queue.Enqueue(nextRow);//x
                    queue.Enqueue(nextCol );//y
                }
            }
            
            
        }
        int min = 0;
        //找time的最大值
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    //还有新鲜的就返回-1

                    return -1;
                }
                min =Math.Max(min, time[i][j]) ;

               
            }
        }

        return min;

    }
    }
class Program994
{
    static void Main994(string[] args)
    {
      int[][]  grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]];
        Solution994 solution = new Solution994();
       int res= solution.OrangesRotting(grid);
        Console.WriteLine(res);
    }
}
